package string.leetcode.easy;

/**
 * @author bruin_du
 * @description 翻转单词顺序
 * @date 2022/5/26 20:57
 **/
public class Offer58I_ReverseWords {
    public static String reverseWords(String s) {
        //方法一：不使用API实现
         return method1(s);

         //方法二：使用API实现
//        method2(s);
    }
    public static String method1(String s) {
        if(s == null || s.length() == 0) return s;

        //去除中间和前后的空格
        StringBuilder sb = trimSpace(s);

        //将整个字符串进行翻转
        reverse(sb,0,sb.length() - 1);
        return sb.toString();
    }

    private static StringBuilder trimSpace(String s) {
        int start = 0,end = s.length() - 1;
        //跳过前后的空格
        while(start < s.length() && s.charAt(start) == ' ') start++;
        while(end >= 0 && s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        int left = 0,right = 0;
        for (int i = start; i <= end; i++) {
            while(i <= end && s.charAt(i) == ' ') i++;
            left = i;
            while(i <= end && s.charAt(i) != ' ') i++;
            right = i;
            //在[left,right)区间中为单词,如果两者相等说明没有需要处理的单词
            //比如全是空格的情况
            if(left != right) {
                sb.append(s,left,right);
                //将刚拼接的字符串进行反转,right - left就是本次拼接的单词长度
                //sb.length() - (right - left)就是单词的起始位置,sb.length() - 1为单词的末尾
                reverse(sb,sb.length() - (right - left),sb.length() - 1);
                //在单词之间加上空格
                if(right != end + 1)
                    sb.append(' ');
            }
        }
        return sb;
    }

    //翻转改区间上的字符串
    private static void reverse(StringBuilder sb, int start, int end) {
        while(start < end){
            char tmp = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,tmp);
            start++;
            end--;
        }
    }

    //使用API
    private static String method2(String s) {
        String[] str=s.trim().split("\\s+");  //删除首尾的空格，然后分隔字符串
        StringBuilder sb=new StringBuilder();
        for(int j=str.length-1;j>=0;j--){
            sb.append(str[j]).append(" ");
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(reverseWords("    "));
    }
}
